/**
 * 76. 最小覆盖子串
 * https://leetcode-cn.com/problems/minimum-window-substring/
 */
public class Solutions_76 {
    public static void main(String[] args) {
//        String S = "ADOBECODEBANC", T = "ABC";  // output: "BANC"
//        String S = "ABECOBAC", T = "ABC";  // output: "BAC"
//        String S = "a", T = "a";  // output: "a"
//        String S = "aa", T = "a";  // output: "a"
        String S = "aa", T = "aa";  // output: "aa"
//        String S = "a", T = "b";  // output: ""

        String result = minWindow(S, T);
        System.out.println(result);
    }

    /**
     * 解法二：滑动窗口优化版（3ms）
     */
    public static String minWindow(String s, String t) {
        char[] sarr = s.toCharArray();
        char[] tarr = t.toCharArray();
        int slen = sarr.length, tlen = tarr.length;
        if (slen < tlen) {
            return "";
        }
        int[] window = new int[128];
        int[] target = new int[128];
        for (char c : tarr) {
            // target[65] = 2，表示字符 'A' 最少需要出现 2 次
            target[c] ++;
        }
        int left = 0, right = 0;
        int start = 0, end = slen + 1;
        // 定义变量：count 记录目标字符串 target 中的字符，在窗口中，可以找到的字符数量
        // 若遍历的字符，在目标字符串 T 中存在，且遍历的字符出现的次数，小于目标字符的次数，那么该字符可以用做匹配，同时 count + 1
        int count = 0;
        char c;
        while (right < slen) {
            c = sarr[right];
            if (target[c] > 0) {
                // 仅该字符在窗口中的出现次数，还小于目标字符的数量时，说明找到一个可以匹配的字符
                count += window[c] < target[c] ? 1 : 0;
                window[c] ++;
                while (count == tlen) {
                    // 窗口中，可以找到全部的目标字符时
                    if (right - left < end - start) {
                        start = left;
                        end = right;
                    }
                    c = sarr[left];
                    if (target[c] > 0) {
                        window[c] --;
                        // 该字符出现次数减 1 后，若小于目标字符的数量时，count 也减 1
                        count -= window[c] < target[c] ? 1 : 0;
                    }
                    left ++;
                }
            }
            right ++;
        }
        String res = "";
        if (end < slen) {
            res = s.substring(start, end + 1);
        }
        return res;
    }

    /**
     * 解法一：滑动窗口（28ms）
     */
    public static String minWindow2(String s, String t) {
        String res = "";
        if (s == null || t == null || s.length() < t.length()) {
            return res;
        }
        char[] sarr = s.toCharArray();
        char[] tarr = t.toCharArray();
        int[] target = new int[128];
        int[] window = new int[128];
        for (char c : tarr) {
            target[c] ++;
        }
        int left = 0, right = 0;
        int len = s.length();
        int minLen = len + 1;

        while (right < len) {
            window[sarr[right]] ++;
            while (check(target, window)) {
                // 滑动窗口中的字符，包含字符串 t 中的全部字符
                int curLen = right - left + 1;
                if (curLen < minLen) {
                    minLen = curLen;
                    res = s.substring(left, right + 1);
                    if (minLen == 1) {
                        // 没有比长度 1 更小的长度了，直接返回结果
                        return res;
                    }
                }
                // 比较结果后，滑动窗口左指针右移，直到滑动窗口中不包含字符串 t 中全部字符
                // 继续查找其他子串
                window[sarr[left]] --;
                left ++;
            }
            right ++;
        }
        return res;
    }

    public static boolean check(int[] target, int[] window) {
        for (int i = 0; i < 128; i++) {
            // 滑动窗口中的元素个数小于目标数量，说明窗口中未包含全部的目标字符
            if (window[i] < target[i]) {
                return false;
            }
        }
        return true;
    }
}
